package dp;

import java.util.Arrays;

/**
 * 416. 分割等和子集
 */
public class P416 {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if ((sum & 1) == 1) {
            return false;
        }
        int len = nums.length;
        int target = sum / 2;
        int[][] dp = new int[len + 1][target + 1];
        for (int i = 1; i <= len; i++) {
            int num = nums[i - 1];
            for (int j = 0; j <= target; j++) {
                if (j == num) {
                    dp[i][j] = 1;
                } else if (j > num) {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[len][target] != 0;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 5, 11, 5};
        boolean flag = new P416().canPartition(nums);
        System.out.println(flag);
    }
}
